///**
// *
// */
//package hihocoder;
//
//import java.util.Arrays;
//import java.util.Collections;
//import java.util.HashMap;
//import java.util.PriorityQueue;
//import java.util.Scanner;
//
///**
// * @author zhongfang
// *
// */
//public class 锟斤拷锟斤拷锟皆癸拷 {
//
//	static class PosKeys implements Comparable<PosKeys>{
//		int x;
//		int y;
//		int keys;
//		int val=-1;
//
//		public PosKeys(int x,int y,int keys) {
//			this.x=x;
//			this.y=y;
//			this.keys=keys;
//		}
//		public PosKeys(int x,int y,int keys,int val) {
//			this.x=x;
//			this.y=y;
//			this.keys=keys;
//			this.val=val;
//		}
//
//		@Override
//		public int compareTo(PosKeys o) {
//			return this.val-o.val;
//		}
//
//		@Override
//		public int hashCode() {
//			String s=x+""+y+keys;
//			return s.hashCode();
//		}
//
//		@Override
//		public boolean equals(Object obj) {
//			PosKeys oKeys=(PosKeys)obj;
//			return this.x==oKeys.x&&this.y==oKeys.y&&this.keys==oKeys.keys;
//		}
//	}
//	static char[][] theMatrix;
//	static int[][] locksPos;
//	static int[][] neibors = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
//
//	public static int getRes(int[] start, int[] end, char[][] matrix, int[][] locks) {
//		theMatrix = matrix;
//		locksPos = locks;
//		int lockStatusNums = 1 << locks.length;
//		// 拥锟斤拷锟斤拷状态00000锟斤拷00001锟斤拷00010
////		int[][][] dp = new int[matrix.length][matrix[0].length][lockStatusNums];
////		for (int i = 0; i < dp.length; i++) {
////			for (int j = 0; j < dp[0].length; j++) {
////				for (int j2 = 0; j2 < lockStatusNums; j2++) {
////					dp[i][j][j2] = -1;
////				}
////			}
////		}
////		dp[start[0]][start[1]][0] = 0;
////
////		BFS(dp, start, 0);
////		int min = Integer.MAX_VALUE;
////		for (int is : dp[end[0]][end[1]]) {// 锟斤拷同锟斤拷状态
////			if (is != -1) {
////				min = Math.min(min, is);
////			}
////		}
////		return min == Integer.MAX_VALUE ? -1 : min;
//		int n=matrix.length;
//		int m=matrix[0].length;
//		PriorityQueue<PosKeys> queue=new PriorityQueue<>();
//		PosKeys sss=new PosKeys(start[0], start[1], 0,0);
//		queue.add(sss);
//		HashMap<PosKeys,Integer> allPos=new HashMap<>(n*m*lockStatusNums);
//		allPos.put(sss,0);
//		while (!queue.isEmpty()) {
//			PosKeys posKeys=queue.poll();
//			int[] startCur=new int[]{posKeys.x,posKeys.y};
//			int lockStatus=posKeys.keys;
//			int cost=posKeys.val;
//			int newCost = cost + 1;
//			for (int i = 0; i < neibors.length; i++) {
//				int newX = neibors[i][0] + startCur[0];
//				int newY = neibors[i][1] + startCur[1];
//				if (newX >= n || newX < 0 || newY >= m || newY < 0) {// 越锟斤拷
//					continue;
//				}
//				if (theMatrix[newX][newY] == '#') {
//					continue;
//				}
//				if (theMatrix[newX][newY] != '.') {// 锟斤拷锟斤拷锟斤拷
//					int index = theMatrix[newX][newY] - 'A';// 锟斤拷锟斤拷锟�
//					// 锟斤拷锟斤拷欠锟斤拷锟皆匡拷锟�
//					if ((lockStatus & (1 << index)) == (1 << index)) {// 锟斤拷钥锟阶ｏ拷锟斤拷锟皆斤拷锟斤拷
////						theMatrix[newX][newY] = '.';//锟斤拷锟斤拷锟斤拷锟斤拷锟皆的革拷
//					} else {// 锟斤拷锟杰达拷锟斤拷,锟斤拷锟斤拷锟斤拷锟脚ｏ拷锟斤拷锟杰斤拷锟斤拷
//						continue;
//					}
//				}
//				PosKeys next=new PosKeys(newX,newY,lockStatus);
//				if (!allPos.containsKey(next) || allPos.get(next) > newCost) {
//					int newLockStatus = lockStatus;
//					// 锟斤拷锟斤拷锟角凤拷锟斤拷钥锟斤拷
//					for (int j = 0; j < locksPos.length; j++) {
//						boolean keyTag = (newX == locksPos[j][0] && newY == locksPos[j][1]);
//						if (keyTag) {// 锟斤拷j锟斤拷锟斤拷锟斤拷钥锟斤拷,锟窖碉拷j位锟斤拷锟斤拷为1
//							int tttmp = 1 << j;
//							if ((newLockStatus & (tttmp)) == 0) {
//								newLockStatus += tttmp;
//							}
//						}
//					}
//					dp[newX][newY][newLockStatus] = newCost;
////					System.out.println(newX+" "+newY+" "+newLockStatus+" "+newCost);
////					BFS(dp, new int[] { newX, newY }, newLockStatus);
//					queue.add(new PosKeys(newX, newY, newLockStatus, newCost));
//				}
//			}
//		}
//		return lockStatusNums;
//	}
//
//	private static void BFS(int[][][] dp, int[] start, int lockStatus) {
//		// 锟斤拷锟斤拷锟斤拷围锟斤拷状态
//		int newCost = dp[start[0]][start[1]][lockStatus] + 1;
//		for (int i = 0; i < neibors.length; i++) {
//			int newX = neibors[i][0] + start[0];
//			int newY = neibors[i][1] + start[1];
//			if (newX >= dp.length || newX < 0 || newY >= dp[0].length || newY < 0) {// 越锟斤拷
//				continue;
//			}
//			if (theMatrix[newX][newY] == '#') {
//				continue;
//			}
//			if (theMatrix[newX][newY] != '.') {// 锟斤拷锟斤拷锟斤拷
//				int index = theMatrix[newX][newY] - 'A';// 锟斤拷锟斤拷锟�
//				// 锟斤拷锟斤拷欠锟斤拷锟皆匡拷锟�
//				if ((lockStatus & (1 << index)) == (1 << index)) {// 锟斤拷钥锟阶ｏ拷锟斤拷锟皆斤拷锟斤拷
////					theMatrix[newX][newY] = '.';//锟斤拷锟斤拷锟斤拷锟斤拷锟皆的革拷
//				} else {// 锟斤拷锟杰达拷锟斤拷,锟斤拷锟斤拷锟斤拷锟脚ｏ拷锟斤拷锟杰斤拷锟斤拷
//					continue;
//				}
//			}
//			if (dp[newX][newY][lockStatus] == -1 || dp[newX][newY][lockStatus] > newCost) {
//				int newLockStatus = lockStatus;
//				// 锟斤拷锟斤拷锟角凤拷锟斤拷钥锟斤拷
//				for (int j = 0; j < locksPos.length; j++) {
//					boolean keyTag = (newX == locksPos[j][0] && newY == locksPos[j][1]);
//					if (keyTag) {// 锟斤拷j锟斤拷锟斤拷锟斤拷钥锟斤拷,锟窖碉拷j位锟斤拷锟斤拷为1
//						int tttmp = 1 << j;
//						if ((newLockStatus & (tttmp)) == 0) {
//							newLockStatus += tttmp;
//						}
//					}
//				}
//				dp[newX][newY][newLockStatus] = newCost;
////				System.out.println(newX+" "+newY+" "+newLockStatus+" "+newCost);
////				BFS(dp, new int[] { newX, newY }, newLockStatus);
//				queue.add(new PosKeys(newX, newY, newLockStatus, newCost));
//			}
//		}
//	}
//
//	/**
//	 * @param args
//	 */
//	public static void main(String[] args) {
//		Scanner scanner = new Scanner(System.in);
//		int N = scanner.nextInt();
//		int M = scanner.nextInt();
//		char[][] matrix = new char[N][M];
//		int K = scanner.nextInt();
//		int[] start = new int[2];
//		int[] end = new int[2];
//		start[0] = scanner.nextInt();
//		start[1] = scanner.nextInt();
//		end[0] = scanner.nextInt();
//		end[1] = scanner.nextInt();
//		scanner.nextLine();
//		for (int i = 0; i < N; i++) {
//			String string = scanner.nextLine();
//			for (int j = 0; j < M; j++) {
//				matrix[i][j] = string.charAt(j);
//			}
//		}
//		int[][] locks = new int[K][2];
//		for (int i = 0; i < K; i++) {
//			locks[i][0] = scanner.nextInt();
//			locks[i][1] = scanner.nextInt();
//		}
//		scanner.close();
//		System.out.println(getRes(start, end, matrix, locks));
//		Character[] s=new Character[4];
//		Arrays.sort(s,Collections.reverseOrder());
//	}
//
//}
